package LeetCode;

import java.awt.print.Pageable;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}19:41
 */
public class LeetCode437 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    //要使用双重递归
    public int pathSum(TreeNode root, int sum) {
        if (root == null){
            return 0;
        }
        //当根节点在路径中
        int res = findPath(root,sum);
        res += pathSum(root.left,sum);
        res += pathSum(root.right,sum);

        return res;
    }

    public int findPath(TreeNode node,int sum){
        if (node == null){
            return 0;
        }
        int res = 0;
        if (node.val == sum){// 这里其实相当于减少了一次递归
            res += 1;//这里不直接返回 是防止后面有负数导致还有可能等于sum
        }

        res += findPath(node.left,sum - node.val);
        res += findPath(node.right, sum - node.val);

        return res;
    }

    public int pathSum2(TreeNode  root,int sum){
        if (root == null){
            return 0;
        }
        int res = findPath2(root,sum);
        res += pathSum2(root.left,sum);
        res += pathSum2(root.right,sum);
        return res;
    }

    public int findPath2(TreeNode root,int sum){
        if (root == null){
            return 0;
        }
        int res = 0;
        if (root.val == sum){
            res += 1;
        }
        res += findPath2(root.left,sum - root.val);
        res += findPath2(root.right,sum - root.val);
        return res;
    }
}
